Low-Density Parity-Check (LDPC) codes have attracted much attention in the past several years due to their outstanding error-correction performance.
Nowadays, LDPC codes are used in several modern communication standards, including G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable), IEEE 802.3an (10 Giga-bit/s Ethernet over Twisted pair), IEEE 802.16e (WiMAX standard for microwave communications), IEEE 802.11n-2009 (Wi-Fi standard), CMMB (China Multimedia Mobile Broadcasting), DVB-S2/DVB-T2/DVB-C2 (Digital video broadcasting, 2nd Generation), DMB-T/H (Digital video broadcasting), DOCSIS 3.1 (Data Over Cable Service Interface Specification).
LDPC codes are linear codes characterized by a sparse parity-check matrix H, that is a parity-check matrix in which the number of non-zero elements is relatively small compared to the size M×N of the matrix.
A LDPC code is generally decoded by an iterative message passing algorithm operating on the Tanner graph representing the code. More specifically, the LDPC code can be represented by a bipartite graph comprising a plurality M of check nodes (each check node representing a parity check equation) and a plurality N of variable nodes (each variable node representing a bit of a codeword), a non-zero element in the parity-check matrix being associated to an edge of the graph. The decoding algorithm involves an iterative exchange of information about the likelihood of the bits (e.g. belief propagation algorithm) over the edges of the graph. The decoding algorithm is implemented by check node units or CNUs (corresponding to the parity check equations) and variable node units or VNUs (corresponding to the codeword bits).
In modern communication systems, there is a constant need for increasing the data rate combined with a requirement of reducing power consumption. Iterative decoding of LDPC codes suffers from a high latency issue, stemming from the fact that the decoding iterations need to be performed sequentially, therefore limiting the transmission throughput. In order to reduce latency, it is important to limit the number of decoding iterations that is needed to correct the channel errors. Since the average number of iterations to decode a noisy codeword is typically much smaller than the maximum allowed iterations, especially for long codes, stopping the decoder earlier may lead to significant reduction in latency and energy consumption. Therefore, an important feature of LDPC decoders/decoding methods lies in the criterion used to stop the decoding process, i.e. when it is possible to declare that convergence to the correct codeword has been achieved.
Stopping criteria can be classified in two main categories. The stopping criteria of the first category operate on the soft values of the decoded bits, namely the AP-LLRs (A Posteriori Log-Likelihood Ratios). The stopping criteria of the second category operate on the hard decided bits and perform a parity-check computation.
The stopping criteria of the first category may usually be applied on-the-fly, namely without interrupting the decoding process. However, they lead to residual errors.
By contrast, the stopping criteria of the second category generally require to interrupt the decoding process, to make a hard decision on the AP-LLRs and to calculate the syndrome. They lead to a lower BER at the cost of extra latency, though.
Recently a class of LDPC codes, called QC-LDPC codes (Quasi-Cyclic LDPC codes) or protograph codes, has received considerable attention in the literature. A QC-LDPC code is a LDPC code whose parity-check matrix is defined by blocks of circulant matrices. A detailed description of the QC-LDPC codes can be found in the article of M. Fossorier entitled “Quasi-Cyclic Low-density Parity Check Codes from circulant permutation matrices” published in IEEE Trans. on Information Theory, vol. 50, No. 8, August 2004, pp. 1788-1793. A QC-LDPC code is defined by base matrix B of size R×C having integer elements br,c≥−1, ∀r=0, . . . , R−1 and ∀c=0, . . . , C−1. The parity check matrix H is obtained by expanding the base matrix by an expanding factor L, each element of B being replaced by square matrix of size L×L as follows:
if br,c=−1, br,c is replaced with an all-zero matrix 0L×L 
if br,c≥0, br,c is replaced with a circulant matrix CS(br,c) obtain by right-shifting the rows of the identity matrix IL×L by br,c positions (in particular, an element br,c=0 is replaced by IL×L). Equivalently, br,c is replaced with Jbr,c where J is the cyclic permutation matrix of size L×L
  J  =      (                            0                          0                          …                          0                          1                                      1                          0                          ⋱                          0                          0                                      0                          ⋱                          ⋱                          ⋮                          ⋮                                      ⋮                          ⋱                          ⋱                          0                          0                                      0                          0                          …                          1                          0                      )  and recalling that J0=IL×L. The resulting parity-check matrix H has therefore M=L×R rows and N=L×C columns.
An example of construction of the parity-check matrix H of a QC-LDPC code has been illustrated in FIG. 1. In this example, the base matrix is of size 4×24, the expansion factor being designated by L.
An important feature of a QC-LDPC code is that its parity-check matrix is organized in layers, a layer being defined as set of L consecutive rows of H originating from one row of B. In the following, we denote Hr the sub-matrix of H corresponding to the rth row of B. From the construction of H, it appears that a variable node occurs at most once in a parity check layer Hr. Stated differently, if we denote xj, j=1, . . . , N the bits of a codeword, the parity-check equations corresponding to a layer r do not involve more than once each bit xj. By contrast, the parity-check equations corresponding to two distinct layers of H may involve twice the same bit xj. This layered structure considerably simplifies the hardware of the decoder: all CNUs within one layer may operate in parallel and all messages computed by the CNUs can then be propagated in one pass (one clock cycle) to the VNUs linked thereto for processing the next layer. Hence the message-passing can be performed layer by layer instead of row by row as in a conventional LDPC decoder. This message propagation scheduling, also known more simply as layered scheduling, converges in about half the number of iterations compared to the fully parallel decoder, thus yielding a lower decoding latency. Furthermore, the same processing units (CNUs, VNUs) can be reused to process all the layers of the parity check matrix, thus resulting in an efficient use of the hardware resources. A description of the layered decoder can be found in the article of D. E. Hocevar entitled “A reduced complexity decoder architecture via layered decoding of LDPC codes” published in Proc. of IEEE Workshop on Signal Processing Systems (SIPS), 2004, pp. 107-112.
Stopping criteria designed for decoding LDPC codes can obviously be applied in particular to QC-LDPC codes. Hence, a classical criterion would be to interrupt the decoding at the end of an iteration, once all the layers have been processed, and to calculate the syndrome on the decided word {circumflex over (x)}=({circumflex over (x)}1, {circumflex over (x)}2, . . . {circumflex over (x)}N), where {circumflex over (x)}1, {circumflex over (x)}2, . . . {circumflex over (x)}N are the hard-decided bits:s=H{circumflex over (x)}T  (1)the syndrome s being represented as a vector of size M. This approach, also called full syndrome approach, leads to a latency overhead since the decoding has to be interrupted. Alternatively, we may consider using an additional hard decision memory for storing the hard-decided bits and performing the syndrome computation while the next iteration is being processed. However, such an implementation would imply additional memory and cost overhead.
Specific stopping criteria have been designed for taking advantage of the hardware architecture of QC-LDPC decoder. More specifically, it has been proposed to use partial syndromes as a measure to stop the decoding.
A partial syndrome, denoted sr, is a vector of size L associated with a layer r, defined by the L parity-check equations within this layer, that is:sr=Hr{circumflex over (x)}T  (2)If all the partial syndromes sr, r=0, . . . , R−1 are null, then it is assumed that {circumflex over (x)} is a codeword and the decoding stops.
The computation of the partial syndromes can be performed on-the-fly as described by E. Amador et al. in the article entitled “On-the-fly syndrome check for LDPC decoders”, published in Proc. 6th Int'l Conf. on Wireless and Mobile Communications (ICWMC), 2010. From an hardware cost point-of-view, the on-the-fly partial syndrome check (also called OTF syndrome) is advantageous since the computation of the sequence of the partial syndromes sr, r=0, . . . , R−1 does not increase the decoding latency, contrary to the full syndrome approach.
However, the OTF syndrome stopping criterion may lead to undetected errors. These errors stem from the fact that variable-nodes are updated after each layer is processed. Therefore, even if sr=0, r=0, . . . , R−1, these syndromes may be calculated on different hard decision vectors {circumflex over (x)}. In other words, there is no guarantee that the partial syndromes are satisfied by the same hard decided word. In such instance, the output hard decision vector is not a codeword. Hence, the OTF stopping criterion leads to a dramatic increase of the FER (Frame Error Rate) at medium to high SNR, more precisely in the waterfall region.
The article of A. Hera et al. entitled “Analysis and implementation of the on-the-fly stopping criteria for layered QC LDPC decoders” published in Proc. of the 22nd Int'l Conf. on Mixed Designs of Integrated Circuits and Systems (MIXDES), Torun, Poland, June 2015, pp. 287-297, reviews the existing on-the-fly criteria for early termination of LDPC decoding and proposes a new criterion (called on-the-fly imprecise parity check or OTF-IPC) to improve the performance of the OTF. The OTF-IPC generalizes the OTF by taking into account a plurality k of consecutive iterations. More specifically, if sr(l) denotes the partial syndrome calculated on the layer r at the iteration l, the OTF-IPC criterion proposes to stop the decoding when sr(l)=sr(l+1)= . . . =sr(l+k+l)=0L, for a plurality λ of consecutive layers r=r0, r0+1, . . . , r0+λ, where 0L is a vector of size L with all-zero elements. By increasing the number k of consecutive iterations, the FER is improved at the cost of higher latency.
The article of J.li et al. entitled “Memory efficient layered decoder design with early termination for LDPC codes”, published in Proc. IEEE International Symposium on Circuits and System (ISCAS), 2011, proposes a low complexity early termination strategy for layered decoding based on monitoring the fluctuation of the hard decision vector from one layer to another. The stopping criterion is referred to as sign stability or SS, since the hard decision vector is given by the signs of the AP-LLR values. After processing a given layer, the signs of the newly obtained AP-LLRs are compared to the ones of the previous layer. If this comparison does not yield a sign change, a counter is incremented by 1. Otherwise, if at least one of the signs changes during current layer processing, the counter is reset (set to 0). The stopping condition is satisfied when the counter reaches a value equal to the number of layers.
Even if there is no guarantee that the output hard decision vector is a codeword (since no syndrome check is performed), it turns out that this stopping criterion is safer than the one based on the OTF syndrome, in the sense that it introduces almost no degradation of the error correction performance. However, the SS stopping criterion leads to an increased latency, i.e. it takes longer than the classical full syndrome check to stop decoding, as a high number of decoding iterations is required before the AP-LLR signs completely stop fluctuating.
The purpose of the present application is therefore to propose a new criterion for stopping the decoding of a QC-LDPC code, and more generally of a layered LDPC code, which neither entails memory overhead nor leads to a high latency, this without sacrificing the error rate.